%Model matematyczny problemu

\section{Wejście}

Na wejściu problemu mamy zbiór stanów - odpowiadających kolorom na planszy:

\begin{equation}
	S = \{0, 1, ..., l\} \qquad l \in \mathbb{N}
\end{equation}

Zero oznacza brak klocka w danym polu.

Oraz macierz wejściową $M$, reprezentującą planszę:

\begin{eqnarray}
	M \in M_{m\times n} & \textrm{dla} & m, n \in \mathbb{N} \\
	M_{i,j}\in	S & \textrm{dla} & i \in [0, m), j \in [0, n)
\end{eqnarray}

\section{Wynik}

Wynikiem jest sekwencja współrzędnych:

\begin{eqnarray}
	R = (w_1, w_2, ..., w_k)  & \textrm{dla} & k \in \mathbb{N} \\
	w_i = (x_i, y_i) & \textrm{dla} & x \in [0, m), y \in [0, n)
\end{eqnarray}

Minimalizowana będzie ilość niezerowych elementów na planszy:

\begin{eqnarray}
	N & \textrm{zbiór elementów niezerowych} \\
	\forall_{v_i = (x_i, y_i)} & v_i \in N \Leftrightarrow E_{v_i} \neq 0 
\end{eqnarray}

\section{Warunki dodatkowe}

Sekwencja wynikowa musi spełniać następujący warunek: musi generować sekwencję kroków $k_i$, takich że:

\begin{equation}
	M_0 \xrightarrow{k_1} M_1 \xrightarrow{k_2} M_2 \xrightarrow{k_3} ... \xrightarrow{k_r} E
\end{equation}

Gdzie:
\begin{eqnarray}
	E & - & \textrm{macierz wynikowa} \\
	M_i & - & \textrm{macierz wejściowa po i-tym przekształceniu}
\end{eqnarray}

Macierz końcowa $E$ musi spełniać następujący warunek:

\begin{equation}
	\forall_{p_i = (x_i, y_i)} \colon E_{p_i} \neq 0 \Rightarrow o_t(w_i) = \emptyset
\end{equation}

Operacja otoczenia $o_t(w_i)$ jest zdefiniowana przy operacji wyszukania (patrz \ref{seq:search}).

Krok jest zdefiniowany jako:

\begin{equation}
	k_i \colon (M_{i-1}, w_i) \to M_{i}
\end{equation}

\subsection{Krok algorytmu}

Każdy krok $k_i$ jest złożony z dwóch przekształceń - wyszukania $s_i$ i eliminacji $e_i$.

\subsubsection{Operacja wyszukania}
\label{seq:search}

Operacja wyszukania wyznacza zbiór współrzednych bedącym otoczeniem współrzędnej $w_i$.
\begin{equation}
	s_i \colon (M_{i-1}, w_i) \to W
\end{equation}

Gdzie:
\begin{eqnarray}
	& & W = \{d_1, d_2, ... , d_k\} \\
	& \forall_{d_i \in W} & d_i \in o_t(w_i)
\end{eqnarray}

Żeby zdefiniować otoczenie $o_t(w_i)$ najpierw trzeba wprowadzić pojęcie najbliższego otoczenia $n_{ot}(w_i)$:
\begin{eqnarray}
	& n_{ot}(w_i) \colon \{o_1, ... , o_k\} \\
	\forall_{o_j = (x_j, y_j)} & (|x_j - x_i| = 1 \oplus |y_j - y_i| = 1) \land M_{o_j} = M_{w_i}
\end{eqnarray}

Zbiór będący otoczeniem $w_i$ budujemy w nastepujący sposób:
\begin{enumerate}
	\item Tworzymy pusty zbiór W.
	\item Dodajemy do zbioru najbliższe otoczenie $w_i$.
	\item Rozszerzamy zbiór o najbliższe otoczenie wszystkich jego elementów.
	\item Powtarzamy krok 3 do momentu w którym zbiór przestanie się powiększać.
\end{enumerate}

\subsubsection{Operacja eliminacji}

Operacja eliminacji przekształca macierz wejściową na podstawie zbioru $W$ wyznaczonego przez operację wyszukania.
\begin{equation}
	e_i \colon (M_{i-1}, W) \to M_{i}
\end{equation}

Operacja ta aplikuje następujące przekształcenie:

\begin{equation}
	\forall_{d_i \in W} \colon o_t(d_i) \neq \emptyset \qquad d_i = (x_i, y_i) \nonumber
\end{equation}

\begin{equation}
	\left\{\begin{array}{lll}
		M^{i+1}_{x,y+1} = M^{i}_{x,y} & \textrm{dla} & x = x_i \land y < y_i\\
		M^{i+1}_{x,y} = 0 & \textrm{dla} & x = x_i \land y = 0\\
		M^{i+1}_{x,y} = M^{i}_{x,y} & \textrm{dla reszty} & x, y\\
	\end{array}\right.
\end{equation}

Gdzie:
\begin{eqnarray}
	M^{i}_{x,y} & - & \textrm{Macierz $M$ w kroku $i$, komórka o współrzędnych } (x, y)\\
	M^{i+1}_{x,y} & - & \textrm{Macierz $M$ w kroku $i+1$, komórka o współrzędnych } (x, y)
\end{eqnarray}